Since the early 1990's, the World Wide Web (the “web”) has grown exponentially to include billions of web pages. Web analytics is the collection and analysis of web data in order to optimize user experiences and the usage of the web. The application of web analytics can help providers and content developers understand the dynamics of the web and gain insights into how visitors interact with their websites.
Web graph analysis typically involves the study of the patterns of links between web pages through the application of graph theory in which the links represent edges and the pages represent vertices (or nodes) in the graph. Finding the shortest path between vertices in a web graph is a common problem having applications, for example, to computer networking, web searching, Internet security, online applications such as social networking, and various types of computations and analyses.
While the shortest path problem has been widely studied, existing path finding techniques often scale poorly when applied to web graphs which may have billions of vertices. In particular, some existing techniques can be expensive in terms of processing time when running a query to find the shortest path between two given vertices. Other existing techniques may provide more reasonable query times but may be expensive in terms of storage and/or memory overhead. And some techniques may be reasonably well suited to finding short paths in planar networks (such as those used in mapping and direction-finding applications), but do not perform well with web graphs and other graphs that may have extremely high degree nodes (i.e., those nodes that have a relatively large number of edges to and from them).
This Background is provided to introduce a brief context for the Summary and Detailed Description that follow. This Background is not intended to be an aid in determining the scope of the claimed subject matter nor be viewed as limiting the claimed subject matter to implementations that solve any or all of the disadvantages or problems presented above.